package struct;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LFUCache {

    public static void main(String[] args) {
        LFUCache lfu = new LFUCache(2);
        lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
        lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        System.out.println(lfu.get(1));      // 返回 1
        // cache=[1,2], cnt(2)=1, cnt(1)=2
        lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        // cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.println(lfu.get(2));      // 返回 -1（未找到）
        System.out.println(lfu.get(3));      // 返回 3
        // cache=[3,1], cnt(3)=2, cnt(1)=2
        lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        // cache=[4,3], cnt(4)=1, cnt(3)=2
        System.out.println(lfu.get(1));      // 返回 -1（未找到）
        System.out.println(lfu.get(3));      // 返回 3
        // cache=[3,4], cnt(4)=1, cnt(3)=3
        System.out.println(lfu.get(4));      // 返回 4
        // cache=[3,4], cnt(4)=2, cnt(3)=3
    }

    private int capacity;
    private Bucket head;
    private Bucket tail;
    private Map<Integer, Bucket> buckets;
    private Map<Integer, Integer> keyValMap;

    public class Bucket {
        public int count;
        public Bucket next;
        public Bucket prev;
        public LinkedList<Integer> commands;

        public Bucket(int command, int count) {
            this.count = count;
            this.commands = new LinkedList<>();
            this.commands.add(command);
        }

        public Bucket getNextStoreBucket(int command) {
            if (this.count + 1 == this.next.count) {
                this.next.commands.addLast(command);
                return this.next;
            }
            Bucket newBucket = new Bucket(command, this.count + 1);
            this.linkedLast(newBucket);
            return newBucket;
        }

        public void linkedLast(Bucket bucket) {
            bucket.prev = this;
            bucket.next = this.next;

            // 由于 this.next.prev 受 this.next = bucket 影响，语序不能颠倒
            this.next.prev = bucket;
            this.next = bucket;
        }

        public void linkedPrev(Bucket bucket) {
            bucket.prev = this.prev;
            bucket.next = this;
            this.prev = bucket;
            this.prev.next = bucket;
        }

        public void remove() {
            Bucket next = this.next;
            Bucket prev = this.prev;
            prev.next = next;
            next.prev = prev;
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        buckets = new HashMap<>();
        keyValMap = new HashMap<>(capacity);
        this.head = new Bucket(-1, 0);
        this.tail = new Bucket(-1, Integer.MAX_VALUE);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        if (!keyValMap.containsKey(key)) {
            return -1;
        }

        usedKey(key);
        return keyValMap.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        if (buckets.size() >= this.capacity) {
            removeTarget();
        }

        Bucket currentBucket;
        if (buckets.containsKey(key)) {
            currentBucket = buckets.get(key);
        } else {
            currentBucket = head;
        }

        Bucket storeBucket = currentBucket.getNextStoreBucket(key);
        keyValMap.put(key, value);
        buckets.put(key, storeBucket);
    }

    private void usedKey(int removeCommand) {
        Bucket storeBucket = buckets.get(removeCommand);
        storeBucket.commands.removeFirst();

        Bucket newBucket = storeBucket.getNextStoreBucket(removeCommand);
        buckets.put(removeCommand, newBucket);

        if (storeBucket.commands.isEmpty()) {
            storeBucket.remove();
        }
    }

    public void removeTarget() {

        Bucket storeBucket = head.next;

        LinkedList<Integer> commands = storeBucket.commands;
        Integer removeCommand = commands.removeFirst();
        if (commands.isEmpty()) {
            storeBucket.remove();
        }

        buckets.remove(removeCommand);
        keyValMap.remove(removeCommand);

    }

}
